const arr = [4, 5, 7, 1, 2, 12, 45, 66, 3];

//快速排序 O(nlogN)
function partition(array, start, end) {
    let i = start;
    let piovt = array[end];
    for (let j = start; j <= end; j++) {
        if (array[j] <= piovt) {
            [array[i], array[j]] = [array[j], array[i]];
            i++;
        }
    }
    return i - 1;
}

function quickSort(array, start = 0, end = array.length - 1) {
    if (end - start < 1) return;
    let piovtIndex = partition(array, start, end);
    quickSort(array, start, piovtIndex - 1);
    quickSort(array, piovtIndex + 1, end);
    return array;
}

console.log(quickSort(arr));
